1. Field of the Invention
The present invention relates to an apparatus for selecting an optimum path in a network environment where nodes are distributed and located via a network. More particularly, to an apparatus which estimates and selects an optimum path used to transmit data and its response according to a response times per unit data length of transmission data or of response data when one node transmits service request data to another node among the plural nodes distributed via the network and the response to the transmitted data is returned from the transmission destination node to the transmission source node.
2. Description of the Related Art
With the rapid popularization of the Internet in recent years, the amount of data transmitted/received over the Internet has been significantly increasing. The type and purpose of the data to be transmitted/received over the Internet are diversified. For example, the data of a home page downloaded from a WWW server, the file data of each type of software transmitted from an FTP server, e-mail from a company or an individual are diversified.
In such a situation, Internet users may frequently spend a long time in downloading data from a requested home page, that is, in displaying of the home page, or in downloading a file. This is because the users cannot determine which server is most efficient although mirror servers are provided.
Additionally, since network topology becomes complicated and the node configuration of a network continuously varies, an optimum network path dynamically and significantly changes in its form and its time. Therefore, selecting an optimum path is more difficult for network administrators or network engineers.
However, conventional protocols for selecting a path collect the information such as the number of routers (hop count) interposed between a transmission source address and a transmission destination address, a bandwidth (maximum data flow rate), and traffic (an actual data flow rate), etc., and calculate a path by using these items of information as indices, in each repeater. With these techniques, the response times per unit data length of transmission data and the response data are not used for the calculation of the path selection when one node transmits the data which requests a service to another node and this node returns the data which respond to the transmission data.
As typical examples of the conventional routing protocols, RIP and OSPF can be cited.
The RIP (Routing Information Protocol: RFC 1058) is a dynamic routing information exchange protocol between routers or between a router and a host in an autonomous system. The RIP adopts a distance vector algorithm, and is used by many UNIX systems and routers. According to the RIP, the numbers of routers (hop count) via which data reaches a transmission destination are exchanged between a router and its contiguous router at predetermined time intervals, and a communication path is selected in order to minimize the hop count. Note that the hop count that can be administered is up to 15.
The OSPF (Open Shortest Path First: RFC 1583) adopts a link state algorithm. According to this protocol, network link information (link state) are exchanged between routers, and each of the routers selects an optimum communication path based on the link information. The OSPF can select an optimum cost path in consideration of a network load, a line cost/speed, a delay, etc., and distributes a load by securing paths which costs the same.
Additionally, the example in which a genetic algorithm is applied to the RIP is disclosed as the paper titled xe2x80x9cAn Adaptive Network Routing Algorithm Employing Path Genetic Operators (Seventh International Conference on Genetic Algorithms (ICGA ""97))xe2x80x9d by Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato, et al. in 1997.
The genetic algorithm (GA) is a technique which simulates and applies the mechanism of inheritance of living things. In the evolution of living things, crossover of chromosomes possessed by an individual, or mutation of a gene in a chromosome, may occur when a new individual (child) is born from an old individual (parent). An individual which is not adaptive to an environment is not selected, and an adaptive individual survives and becomes a parent of a new descendant. In this way, a group of individuals which are adaptive to an environment will survive. To what degree each individual will adapt to an environment is determined by a chromosome or a genome.
In the genetic algorithm, a candidate of solution to a combinatorial optimization problem is represented as a character string corresponding to a chromosome which is a one-dimensional string of genes. An optimum solution is searched by repeatedly performing genetic operations such as selection by self-reproduction, crossover, mutation, etc. for a group of solution candidates (referred to as individuals). The above described character string may also be a numeral string represented by, for example, xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d.
Here, the evolution of a living thing corresponds to a process that the value of an objective function (function for evaluating the degree of fitness of a solution candidate) for a solution candidate approaches an optimum value. A fitness degree function whose value is larger as it makes the objective function more optimum is defined for a character string (chromosome). The selection operation is an operation for calculating the evaluation value of each character string by using the fitness degree function, choosing a character string with a high evaluation value from the group of solution candidates, and defining the selected string as a group of solution candidates of a next generation. The mutation operation is an operation for replacing some bits (some genes) included in a character string (bit string) with their values inverted at random (if the original bit is xe2x80x9c1xe2x80x9d, it is replaced with xe2x80x9c0xe2x80x9d, and vice versa). The crossover operation is an operation for exchanging parts of two character strings.
By repeating these operations, a character string with a higher evaluation value, that is, a solution candidate for further optimizing the objective function can be obtained. Genetic algorithms are said to be suitable for solving an optimization problem of a discrete variable, which is large-scaled and multi-peaked, and moreover, they can be easily applied to the above described optimization problem. Therefore, these algorithms are widely used.
In the above described paper by Munetomo et al., a substitute route is generated by a genetic algorithm which uses the mutation and crossover operations in addition to a default route in a routing table generated in a routing table in such a way that each router minimizes the hop count based on the RIP. The probabilities (frequencies) of thus generated paths are determined according to a communication wait time when each of the paths is used. If the evaluation value based on the wait time becomes lower than a predetermined value, this genetic algorithm is applied and another new path is generated.
Here, the mutation operation indicates an operation for changing, for example, one router to its contiguous router among routers structuring a path, and forming a new path by connecting the shortest path between the changed router and a transmission source node and the shortest path between the router and a transmission destination node. The crossover operation is an operation for choosing a combination of routers included in both of the above described pair of paths, choosing one router from the combination, replacing all of the routers existing on a route between the router and a transmission destination node; and generating a new path.
Additionally, TOKUGANHEI 5-87597 (Japanese Patent Laid-Open Publication) xe2x80x9cPath Specifying Mechanism of Transaction Processing Serverxe2x80x9d discloses the mechanism for assigning a transaction whose class is the same as that of the transaction of a transaction processing server for performing an optimum process based on a response time of the transaction.
With the above described mechanism, the transaction is divided into classes, for each of which an average response time of the transaction process is calculated. Furthermore, a target response time is set for each of classes, and a performance index is obtained from the target response time for each of the classes.
Upon receiving one transaction, the above described mechanism obtains an estimate performance index when the transaction is processed for each of transaction processing servers which can possibly perform that transaction, and assigns the process of the transaction to the transaction processing server which makes the estimate performance index for all of the classes highest.
With this mechanism, to which server the transaction process is to be assigned is determined based on the response times of previous transaction processes, and the data length and the response time per unit data length, which are used for processing the transaction, are not taken into consideration. Additionally, this mechanism is not intended to control the network path used to transmit the data required for processing the transaction for the server which processes the transaction. As a matter of course, the number of nodes on the network data transmission path between the client and the server which processes the transaction, the difference in the bandwidth of each of communication paths structuring the data transmission path, etc. are not considered.
With conventional path selecting apparatuses, the response times of combinations of all nodes on all paths must be estimated in order to estimate the response time of a combination of arbitrary contiguous paths. To make such estimates, the amounts of passed data at entry and exit must be measured for all of the nodes on all of the paths, and the estimate results must be collected at one point. However, the amounts of passed data cannot be measured depending on a node. Even if the amounts can be measured, they cannot be used for estimating the response time if the notification format of measured data is different.
Additionally, even if a node has the capability for notifying the amounts of passed data, they may not be frequently notified due to a security reason, etc. depending on a node operator. Therefore, with the conventional path selecting apparatuses, the real-time amounts of passed data at a particular node may not exist in many cases, so that the response time cannot be estimated.
Furthermore, the conventional routing protocols for path selection collect the information such as the number of routers (hop count) interposed between a transmission source address and a transmission destination address, a bandwidth (a maximum data flow rate), and traffic (an actual data flow rate), etc., and determines a path by using these items of information as indices in each repeater such as a router, etc. This determination, however, is locally made by each repeater according to the information provided by a router and its contiguous router, and the path is not selected by evaluating the entire performance of the path from the transmission source address to the transmission destination address, which includes also the performances of a network repeater such as a switch, a router, a client, and a server. Accordingly, with the conventional path selecting apparatuses, for example, the switching capability of a router, the cache distribution effect of WWW/PROXY servers, etc. are not considered as performance information, so that an optimum path for a user using a client, that is, the path whose response time to an actual request is short, is not always selected. In addition, since the order of the processing time within a node is conventionally lower than that of a path passage time, the processing time has almost no influence on the estimate of the response time. However, with the recent advent of a LAN (such as a gigabit Ethernet, etc.), a WAN (B-ISDN implemented by an ATM, etc.), or a gigabit router, whose processing speeds are much faster than that of an internal bus of a computer, the processing time within a node has a significant influence on the entire response time.
Furthermore, with the conventional path selecting apparatuses, a repeater contiguous to a client can be selected only in a static manner. That is, it is impossible to select a path in a dynamic manner as the performance of each repeater dynamically varies.
Still further, with the conventional path selecting apparatuses, the cooperative operation between path selecting apparatuses cannot be implemented. For example, it is impossible to determine a repeater depending on a cache type, and to prevent the contents of one cache from existing in repeaters.
Still further, with the conventional path selecting apparatuses, each client can possibly make the same estimate based on the same data if a similar routing algorithm is used by each client. As a result, all clients select the same node as a path, which leads to an extremely degraded response time.
An object of the present invention is to provide an apparatus, a method, and a storage medium for autonomously selecting an optimum path by recording transmission data and response times per unit data length of response data, which is returned from a transmission destination node to a transmission source node, and by estimating the response time for each path by using the recorded information, when the data requesting a service is transmitted from the transmission source node to the transmission destination node.
Another object of the present invention is to provide an apparatus for selecting a path by using an actual response time per unit data length, which is obtained in consideration of the performances of all of repeaters on a path in addition to the performance of a path between nodes.
A path selecting apparatus according to the present invention is a path selecting apparatus for selecting a network path of data transmitted from a transmission source node to a transmission destination node, and a network path of data returned from the transmission destination node to the transmission source node in an environment where nodes are distributed and located via a network. The apparatus comprises: a path calculating unit for obtaining an estimated response time by using estimated information for each path which can link the transmission source node and the transmission destination node, and for transmitting a service request message by using a path with the minimum estimated response time, when the service request message is transmitted from the transmission source node to the transmission destination node in order to request the service of the transmission destination node; a response information managing unit for storing as response information the information about the transmission of the service request message, which includes at least the path over which the message is transmitted and the request data length of the service request message, when the service request message is transmitted by the path calculating unit, and for storing as the response information the information about the reception of the response, which includes at least the data length of the response and the value about the response time required from the transmission of the service request message till the reception of the response, when the response to the service request message is returned from the transmission destination node to the transmission source node; and an estimation information managing unit for updating the contents of the estimated information based on the response information when the response is received by the response information managing unit. With this configuration, the response time of a path can be estimated even if part of the information about the path cannot be obtained, thereby estimating the response time based on the entire response performance of the path, which includes the performances of a network repeater, a client, a server, etc.
A path selecting method according to the present invention is a method for selecting a network path of data transmitted from a transmission source node to a transmission destination node, and a network path of data returned from the transmission destination node to the transmission source node in an environment where nodes are distributed and located via a network. The method comprises the steps of: obtaining an estimated response time by using estimated information for each path which can connect the transmission source node and the transmission destination node, and transmitting a service request message by using a path with the minimum estimated response time, when the service request message is transmitted from the transmission source node to the transmission destination node in order to request the service of the transmission destination node; storing as response information the information about the transmission of the service request message, which includes at least the path over which the message is transmitted and the request data length of the service request message, when the service request message is transmitted by the path calculating unit, and for storing as the response information the information about the reception of the response, which includes at least the data length of the response and the value about the response time required from the transmission of the service request message till the reception of the response, when the response to the service request message is returned from the transmission destination node to the transmission source node; and updating the contents of the estimated information based on the response information when the response is received by the response information managing unit. With this method, the response time of a path can be estimated even if part of the information about the path cannot be obtained, thereby estimating the response time based on the entire response performance of the path, which includes the performances of respective types of nodes on the path such as a network repeater, a client, a server, etc.
A computer-readable storage medium according to the present invention, stores a program implementing the path selecting method for selecting a network path of data transmitted from a transmission source node to a transmission destination node, and a network path of data returned from the transmission destination node to the transmission source node in an environment where nodes are distributed and located via a network, directs a computer to perform the functions of: obtaining an estimated response time by using estimated information for each path which can connect the transmission source node and the transmission destination node, and transmitting a service request message by using a path with the minimum estimated response time, when the service request message is transmitted from the transmission source node to the transmission destination node in order to request the service of the transmission destination node; storing as response information the information about the transmission of the service request message including at least the path over which the message is transmitted and the request data length of the service request message, when the service request message is transmitted by the path calculating unit, and for storing as the response information the information about the reception of the response, which includes at least the data length of the response and the value about the response time required until the reception of the response from the transmission of the service request message, when the response to the service request message is returned from the transmission destination node to the transmission source node; and updating the contents of the estimated information based on the response information when the response is received by the response information managing unit. With this medium, the response time of a path can be estimated even if part of the information about the path cannot be obtained, thereby estimating the response time based on the entire response performance of the path, which includes the performances of respective types of nodes on the path such as a network repeater, a client, a server, etc.